package com.xinwei.leetcode.二叉树;

import java.util.Deque;
import java.util.LinkedList;

// https://leetcode-cn.com/problems/recover-binary-search-tree/
public class _99_恢复二叉搜索树 {
    /**
     * 先找到两个错误的节点，怎么找：用验证二叉搜索树的方法
     */

//    private TreeNode fstError;
//    private TreeNode scdError;
//    public void recoverTree(TreeNode root) {
//
//    }
//
//    public void findErrorNode(TreeNode root, int upper, int lower) {
//        if (root == null) return;
//        if (root.val < upper && root.val > lower) findErrorNode(root.left, root.val, );
//        if (root.val < upper && root.val > lower) findErrorNode(root.right, , );
//    }


    /**
     * 用迭代法进行中序遍历
     * 这道题首先还是得先搞明白交换后都有那些情况
     * 1、交换两个相邻的树， 当pre > root时，一个记下root， 一个记下pre
     * 2、交换两个响铃的数， 当pre > root时，记下pre， 当第二次pre > root时，记下root
     */
    public void recoverTree(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode fstError = null;
        TreeNode scdError = null;
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (prev != null && prev.val > root.val) {
                scdError = root;
                if (fstError == null) {
                    fstError = prev;
                }else {
                    break;
                }
            }
            prev = root;
            root = root.right;
        }
        swap(fstError, scdError);
    }

    private void swap(TreeNode a, TreeNode b) {
        int tmp = 0;
        tmp = a.val;
        a.val = b.val;
        b.val = tmp;
    }
}
